package class05;

import java.util.LinkedList;

/**
 * 判断完全二叉树
 */

public class Code05_IsCBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isCBT(Node head) {
		if (head == null) {
			return true;
		}

		LinkedList<Node> queue = new LinkedList<>();
		boolean leaf = false; // 表示遇到叶节点的事件（即是否遇到过左右两个孩子不双全的节点），当第一次遇到叶节点后变为true
		Node l = null;
		Node r = null;
		queue.add(head);
		while (!queue.isEmpty()) {
			head = queue.poll();
			l = head.left;
			r = head.right;

			/* if语句的部分是对当前节点的操作 */
			if (
					// 条件2：如果遇到过不双全的节点之后，又发现了当前结点居然有孩子
					(leaf && (l != null || r != null))
					||
					(l == null && r != null) // 条件1：如果当前节点有右孩子但没左孩子
				) {
				return false;
			}  // ===> 满足该if语句后，说明该结点一定有左孩子

			/* 只看queue，就是宽度优先遍历 */
			if (l != null) {
				queue.add(l);
			}
			if (r != null) {
				queue.add(r);
			} else { // 即左+NULL的情况，左右孩子不双全，说明遇到了叶节点。  一旦有一个设置为true了，那后续都是true
				leaf = true;
			}
		}
		return true;
	}

}
